package com.ming.learn.from.carl.stack.and.queue;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/*
239. 滑动窗口最大值
 */
public class Of20210102LeetCode239 {
    public static void main(String[] args) {
        System.out.println(maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3));
    }


    /*
    思路： 太多了 见文章吧。。。
     */
    private static List<Integer> maxSlidingWindow(int[] nums, int k) {
        MyQueue239 que = new MyQueue239();
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < k; i++) { // 先将前k的元素放进队列
            que.push(nums[i]);
        }
        result.add(que.front()); // result 记录前k的元素的最大值
        for (int i = k; i < nums.length; i++) {
            que.pop(nums[i - k]); // 滑动窗口移除最前面元素
            que.push(nums[i]); // 滑动窗口前加入最后面的元素
            result.add(que.front()); // 记录对应的最大值
        }
        return result;
    }

}

class MyQueue239 {
    Deque<Integer> deque = new LinkedList<>();

    // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
    // 同时pop之前判断队列当前是否为空。
    void pop(int value) {
        if (!deque.isEmpty() && value == deque.getFirst()) {
            deque.pollFirst();
        }
    }

    // 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
    // 这样就保持了队列里的数值是单调从大到小的了。
    void push(int value) {
        while (!deque.isEmpty() && value > deque.getFirst()) {
            deque.pollLast();
        }
        deque.addLast(value);
    }

    // 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
    int front() {
        return deque.getFirst();
    }
}
